package org.Test;

import org.HashTable.HashTable;
import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

public class TestHashTable {
    @Test
    public void put(){
        HashTable table = new HashTable();
        table.put(1,"zhang","张三");
        table.put(17,"li","李四");
        table.put(2,"wang","王五");

        Assert.assertEquals(3, table.size);
        Assert.assertEquals("张三", table.table[1].value);
        Assert.assertEquals("李四", table.table[1].next.value);
        Assert.assertEquals("王五", table.table[2].value);

        table.put(1,"zhang","张4");
        table.put(17,"li","李5");
        Assert.assertEquals("张4", table.table[1].value);
        Assert.assertEquals("李5", table.table[1].next.value);
    }

    @Test
    public void remove(){
        HashTable table = new HashTable();
        table.put(1,"zhang","张三");
        table.put(17,"li","李四");
        table.put(2,"wang","王五");

        table.remove(17,"zhang");
        Assert.assertEquals(2,table.size);
        Assert.assertEquals("李四",table.table[1].value);
    }

    public static void main(String[] args) {
        TestHashTable table = new TestHashTable();
        System.out.println(Arrays.toString(table.twoSum(new int[]{2,7,11,15} ,9)));


    }


    public int[] twoSum(int[] nums, int target) {
        // 排列数组
        Arrays.sort(nums);
        //求出目标值的分界线
        int mid = findmid(nums,target);
        if(nums[mid] == target){
            int result = find(nums,0,0,mid);
            if(result != -1){
                return new int[]{result,mid};
            }
        }

        //解题
        int result = -1;
        if(mid > nums.length){
            // 后半段小
            for(int i = mid;i < nums.length; i++){
                result = find(nums,i,0,mid - 1);
                if(result != -1){
                    return new int[]{result,i};
                }
            }
        }else{
            // 前半段小
            for(int i = 0;i < mid; i++){
                result = find(nums,i,mid,nums.length - 1);
                if(result != -1){
                    return new int[]{i,result};
                }
            }
        }
        return null;
    }

    private int findmid(int[] nums,int target){
        int i = 0,j = nums.length - 1;
        while(j >= i){
            int mid = (i + j) >> 1;
            if(nums[mid] < target){
                i = mid + 1;
            }else if(target < nums[mid]){
                j = mid - 1;
            }else{
                return mid;
            }
        }
        if(nums[i] < target){
            return ++i;
        }else{
            return i;
        }
    }
    private int find(int[] nums,int target,int a,int b){
        int i = a,j = b;
        while(j >= i){
            int mid = (i + j) >> 1;
            if(target > nums[mid]){
                i = mid + 1;
            }else if(target < nums[mid]){
                j = mid - 1;
            }else{
                return mid;
            }
        }
        return -1;
    }



}
